{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## BFS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 概览\n",
    "- 因图主要的内容就是“关系”或是说“映射”，所以使用散列表来“描述图”，在Python中就是用dict；另外为了实现BFS算法需要借助队列(queue)来完成，因为需要有顺序的检查（按照“度”关系层次的顺序），在Python中使用deque创建双端队列。\n",
    "\n",
    "- 因遍历所有的关系，所以时间复杂度$O(E)$(E为`edge`,边数)； 又使用了一个队列，对每个人进行检查，故时间复杂度为$O(V)$(V为`vertice`，顶点个数)。总的时间复杂度为$O(V+E)$\n",
    "\n",
    "- 用于找出段数最少的路径，即在尽可能少的“度”内找到某元素。\n",
    "\n",
    "- 广度优先搜索可以用来计算非加权图中的最短路径；对应的Dijkstra算法用来计算加权图的最短路径。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 代码实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-28T15:43:42.633029Z",
     "start_time": "2018-12-28T15:43:42.621158Z"
    }
   },
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "# is selller\n",
    "def person_is_seller(name):\n",
    "    return name[-1] == 'm'\n",
    "\n",
    "# bfs:graph为关系图，name为搜索的中心，这里为`you`\n",
    "def bfs(graph, name):\n",
    "    search_queue = deque()\n",
    "    search_queue += graph[name]\n",
    "    searched = []  # 避免无限循环，对检查过的元素进行标记\n",
    "    while search_queue:\n",
    "        person = search_queue.popleft()\n",
    "        if person not in searched:\n",
    "            if person_is_seller(person):\n",
    "                print(person, \" is a mango seller!\")\n",
    "                return True\n",
    "            else:\n",
    "                search_queue += graph[person]\n",
    "                searched.append(person)\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-28T15:43:42.886149Z",
     "start_time": "2018-12-28T15:43:42.881506Z"
    }
   },
   "outputs": [],
   "source": [
    "# 创建图\n",
    "def create_graph():\n",
    "    graph = {}\n",
    "    graph['you'] = ['alice', 'bob', 'claire']\n",
    "    graph['bob'] = ['anuj', 'peggy']\n",
    "    graph['alice'] = ['peggy']\n",
    "    graph['claire'] = ['thom', 'jonny']\n",
    "    graph['anuj'] = []\n",
    "    graph['peggy'] = []\n",
    "    graph['thom'] = []\n",
    "    graph['jonny'] = []\n",
    "    return graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-28T15:44:08.384038Z",
     "start_time": "2018-12-28T15:44:08.356719Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "thom  is a mango seller!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# test\n",
    "bfs(create_graph(), 'you')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
